寫在開始之前

今年以系統程式為主題跳進 Software Development 算是一個大膽的嘗試，對於一個大學時期只有寫過 web 與一些簡單程式的我來說，能在得獎名單上看到自己的作品真的讓我又驚又喜。
在學生時期拿到鐵人賽的個人獎項一直都是我的終極目標之一，我想以自己為例鼓勵大家跳脫舒適圈，或許不經意間就能為你的生活加入許多驚喜！

更新文章哪裡看

我預計會再補上 fork, wait, exit...等系統呼叫的文章，為多執行緒程式做一些基礎的鋪墊。
考慮到鐵人發文按鈕過一陣子就會消失，若之後有文章結構上的大調整或是有其他新文章，我都會優先更新在 AwesomeCS wiki 上，以確保大家可以按照我所期望的順序學習系統程式，還請大家見諒 <(_ _)>

=== 廢話結束 ===

是否要在 C 程式中使用 goto，一直都是工程師之間熱烈討論的話題之一。有人說使用 goto 會破壞程式結構、也有人說都有迴圈了，何必使用 goto 呢？

goto 於大型軟體專案的應用

因為實驗室開發的關係，筆者最近閱讀了一個大型的 c 語言專案，並且碰巧讀到了 Computed goto for efficient dispatch tables 這篇文章，讓我對 goto 有了更深入的認知。
一般來說，goto 如果出現在 C 語言專案，那它有很大的可能是被應用在：

• exception handling
• computed goto

前者可以方便開發者在 C 語言程式出錯時回收動態分配的記憶體，或是進行對應的錯誤處理以確保程式下次進入該函式時仍可以正常工作。
試想，如果一家公司需要開發一個高效能的網路程式，並且要確保該程式可以穩定且持續的工作，這時在軟體中可能發生的錯誤都不能被輕易放過。

以 2021 年 10 月初 Facebook 斷線的例子來看，Facebook 因長達六小時的斷線，連帶損失估計超過 9 億美元，由此可見商業化軟體的穩定性是非常重要的。

至於後者 computed goto，才是筆者想要在本文與大家分享的重點！

computed goto

在先前的淺談分支預測與 Hazards 議題一文中，我們可以歸納出一個重點： 如果分支預測失敗，會導致流水線中已經排序的指令流被清除，這也就表示我們的處理器不止做了白工，還要把正確的指令填充回流水線上面。

再談 branch prediction

現代處理器可能引入如上圖所示的分支預測方法，處理器會以 address 為索引，檢索 Pattern history table 上的歷史紀錄進一步的做出預測。

computed goto 的應用

computed goto 適用於取代 switch case 為基底的 dispatcher，因為 switch 僅會以一個基底作為分派任務的參考，這樣子說可能會有點抽象，讓我們用程式碼來進一步了解這個概念：

while (1) {
        switch (code[pc++]) {
            case OP_HALT:
                return val;
            case OP_INC:
                val++;
                break;
            case OP_DEC:
                val--;
                break;
            case OP_MUL2:
                val *= 2;
                break;
            case OP_DIV2:
                val /= 2;
                break;
            case OP_ADD7:
                val += 7;
                break;
            case OP_NEG:
                val = -val;
                break;
            default:
                return val;
        }
    }

如果以現代處理器的分支預測方式來看，同一段程式碼在不同的週期可能會 jump 到不同的地方，這樣會導致分支預測的成功率下降，並且需要反覆的填充正確的指令到流水線上面。

那 computed goto 會怎麽做呢？讓我們一起看下去：

int interp_cgoto(unsigned char* code, int initval) {

    static void* dispatch_table[] = {
        &&do_halt, &&do_inc, &&do_dec, &&do_mul2,
        &&do_div2, &&do_add7, &&do_neg};
    #define DISPATCH() goto *dispatch_table[code[pc++]]

    int pc = 0;
    int val = initval;

    DISPATCH();
    while (1) {
        do_halt:
            return val;
        do_inc:
            val++;
            DISPATCH();
        do_dec:
            val--;
            DISPATCH();
        do_mul2:
            val *= 2;
            DISPATCH();
        do_div2:
            val /= 2;
            DISPATCH();
        do_add7:
            val += 7;
            DISPATCH();
        do_neg:
            val = -val;
            DISPATCH();
    }
}

• 在 function 內宣告變數時加入 static 關鍵字可以使變數的生命週期延長至程式結束

在 C/C++ 中，在不同的地方使用 static 可能會帶來不同的效果，使用上需要特別注意！

• unary operator && 是 gcc 提供的擴展，它可以搭配 label 使用以取得明確的跳轉位址。
• 配合 goto 可以讓程式訪問 code[] 的結果直接跳轉到它對應的操作。

這樣做的好處顯而易見，computed goto 把 jump 的操作分成了好幾部分，只要正確的訪問 dispatch table，我們的處理器就能更精準的預測到正確的分支。

真實世界的例子

Computed goto for efficient dispatch tables 一文有提到 computed goto 被應用到了哪些知名的軟體上：

• Ruby 1.9 (YARV): also uses computed goto.
• Dalvik (the Android Java VM): computed goto
• Lua 5.2: uses a switch

此外，由 Jserv 老師主導開發的 rv32emu-next 同樣引入了 computed goto 的實作，詳細手法可參考：

• rv32emu-next PR#2
• 2020q3 專題: RISC-V 模擬器

使用前請詳閱公開說明書

由於 unary operator 是 gcc 特別提供的擴展，如果你的 C 語言專案不是由 gcc 編譯，或是有人下載了你的原始碼且採用其他編譯器進行編譯就有可能會造成錯誤。
因此，在使用時可以考慮：

• 寫好 makefile，避免有使用者做出超出預期的行為
• 針對編譯器類別做偵測，如果目標編譯器非 gcc，則使用一般的 switch case

最後，可以在編譯時加入 -fno-gcse 與 -fno-crossjumping，讓 gcc 優化你的原始碼。

Reference

• Computed goto for efficient dispatch tables
• What does a && operator do when there is no left side in C?
• 你所不知道的C語言: goto 和流程控制篇